/**
 * 剑指 Offer 51. 数组中的逆序对
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
function reversePairs(nums) {
  if (nums.length <= 1) {
    return 0;
  }
  const middle = Math.floor(nums.length / 2);
  const children1 = nums.slice(0, middle);
  const children2 = nums.slice(middle);
  let count = reversePairs(children1) + reversePairs(children2);
  let i1 = 0;
  let i2 = 0;
  let i = 0;
  while (i1 < children1.length && i2 < children2.length) {
    if (children1[i1] > children2[i2]) {
      nums[i] = children1[i1];
      i1 += 1;
    } else {
      nums[i] = children2[i2];
      i2 += 1;
      count += i1;
    }
    i += 1;
  }
  while (i1 < children1.length) {
    nums[i] = children1[i1];
    i1 += 1;
    i += 1;
  }
  while (i2 < children2.length) {
    nums[i] = children2[i2];
    i2 += 1;
    i += 1;
    count += i1;
  }
  return count;
}

console.log(reversePairs([7, 5, 6, 4]) === 5);
